#x1, x2, x3 = 0, 1, 3
#eps = 0.01
#f = lambda x : return x^3 - 2*x + 1
#while True:
#    f1, f2, f3 = f(x1), f(x2), f(x3)
#    a1 = 2*(f1 * (x2-x3)+f2*(x2-x1) + f3*(x1-x2))
#    a2 = (f1*(x2^2 - x3 ^2)+ f2 * (x2^2 - x1 ^2)+f3*(x1^2-x2^2)
#    xx = a2/a1
#    if abs(x2-xx)<eps:
#        x = xx
#        f_x = f(xx)
#        break
#    else:
#        if (xx-x1)*(xx-x2)<0:
#            if f(xx) <= f2:
#                x3, x2 = x2, xx
#            else:
#                x1 = xx
#        else:
#            if f(xx) <= f2:
#                x1, x2 = x2, xx
#            else:
#                x3 = xx
#print(x)
#print(f_x)
def linearinterpolation(func, eps, x1, x2, x3):
    f1, f2, f3 = func(x1), func(x2), func(x3)
    a1 = 2*(f1 * (x2-x3)+f2*(x2-x1) + f3*(x1-x2))
    a2 = (f1*(x2**2 - x3**2)+ f2 * (x2**2 - x1**2)+f3*(x1**2-x2**2)
    xx = a2/a1
    if abs(x2-xx)<eps:
        return xx,f_x
    else:
        if (xx-x1)*(xx-x2)<0:
            if func(xx) <= f2:
                return linearinterpolation(func, eps, x1, xx, x2)
            else:
                return linearinterpolation(func, eps, xx, x2, x3)
        else:
            if func(xx) <= f2:
                return linearinterpolation(func, eps, x2, xx, x3)
            else:
                return linearinterpolation(func, eps, x1, x2, x3)

